class TreeNode:
    def __init__(self):
        self.data = None
        self.left_child = None
        self.right_child = None


class Tree:
    def __init__(self, dataset):
        self.root = self.build_node(dataset, 1)

    def build_node(self, dataset, i):
        if i > len(dataset):
            return None

        node = TreeNode()
        node.data = dataset[i - 1]
        node.left_child = self.build_node(dataset, 2 * i)
        node.right_child = self.build_node(dataset, 2 * i + 1)
        return node

    # 宽度优先
    def wild_first(self):
        dataset = [self.root]
        index = 0
        while index < len(dataset):
            data = dataset[index]
            yield data.data

            if data.left_child:
                dataset.append(data.left_child)
            if data.right_child:
                dataset.append(data.right_child)
            index += 1

    # 深度优先
    def deep_first(self):
        dataset = [self.root]
        index = -1
        while abs(index) <= len(dataset):
            data = dataset[index]
            if data.right_child:
                dataset.insert(0, data.right_child)
            if data.left_child:
                dataset.insert(0, data.left_child)
            index -= 1

        return [d.data for d in dataset]

    def access_node(self, node, type=1):
        if type == 1:  # 先序
            yield node.data
        if node.left_child:
            yield from self.access_node(node.left_child)
        if type == 2:  # 中序
            yield node.data
        if node.right_child:
            yield from self.access_node(node.right_child)
        if type == 3:  # 后序
            yield node.data

    # 先序遍历
    def pre_order(self):
        yield from self.access_node(self.root)

    def middle_order(self):
        yield from self.access_node(self.root, type=2)

    def after_order(self):
        yield from self.access_node(self.root, type=3)


x = Tree(['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'])
for data in x.pre_order():
    print(data)
